1. Field of Use
The present invention relates to apparatus used by a cache memory and more particularly to apparatus for replacing information within the locations of such cache memory.
2. Prior Art
It is well known to interpose a cache memory between a central processing unit and main memory. Such arrangements improve the performance of the processing unit by providing fast access to instructions and data stored in the cache memory. During normal operation, when the instructions or data requested by the processing unit are not stored in cache, the block containing the requested information is fetched from main memory. When the cache memory is filled, new blocks replace old blocks resident therein.
While different arrangements may be used to select old blocks of information, a least recently used (LRU) replacement has been one of the most commonly used schemes employed in data and instruction cache units. These units include cache memories and address directory circuits. The memories are organized into a number of levels for storing information in the form of data and instructions for fast access. The directory circuits contain address information for identifying which blocks of instructions and data are stored in the cache memory levels. Generally, the LRU replacement scheme has been implemented using a round robin counter or first in first out (FIFO) array. In such arrangements, the assignment of a group or block of locations is made sequentially.
While such arrangements have been generally easy to implement, they are unable to provide any accurate record of order of block usage. To overcome these disadvantages, one system employs a memory for storing a number of least recently used bits to represent the order of usage of memory locations. This system is disclosed in U.S. Pat. No. 4,334,289.
When implemented as an array, the updating of entries can be time-consuming, particularly when there are a large number of cache level entries. Moreover, the delays in updating reduce cache system performance and result in least recently used approximation.
Accordingly, it is a primary object of the present invention to provide apparatus for replacing information within a memory on a least recently used basis.
It is a further object of the present invention to provide apparatus capable of generating signals for rapid and accurate assignment of levels on a least recently used basis.